/**
 * 给定N，要求满足条件的数对：
 * 1. a + b == N
 * 2. a/b都是非零数，即不含0
 * 
 * 数位DP从高向低
 * 因为要计算加法，且有2个数，所以将数位DP的last改造一下
 * 假设当前N的数位是d
 * 则当前last为
 * last = d + high * 10 - low
 * 其中high是向高位的进位，low是向低位的借位
 * 
 */
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;

using llt = long long;

vector<int> G;
// Dijk, j表示当前向高位进位，必然是0或1
// k表示当前向下借位的值，必然是0或1
llt D[22][2][2];
// high: 向高位的进位
// low: 向低位的借位
// leadx: 是否处在x的前导零
// leady: 是否处在y的前导零
llt dfs(int pos, int high, int low, bool leadx, bool leady){
    if(-1 == pos) { // 没有进借，且x和y均正常，则找到1对
        return 0 == high and 0 == low and not leadx and not leady ? 1 : 0;
    }
    if(not leadx and not leady and -1 != D[pos][high][low]) {
        return D[pos][high][low];
    }
    // last需要改变确定方法，实际上就是本位的目标
    int target = G[pos] + high * 10 - low;
    llt ans = 0;
    
    // 从0开始，因为还有进位与借位
    for(int i=0;i<=target;++i){ 
        int x = i;
        int y = target - x;

        bool nx = 0 == x and leadx;
        bool ny = 0 == y and leady;
        
        if(x >= 10 or y >= 10) continue;
        if(0 == x and not nx) continue;
        if(0 == y and not ny) continue;
        // 当前位向低位的借位，也就是pos-1位的进位
        // 分别用是否借位进行调用
        ans += dfs(pos - 1, low, 1, nx, ny);
        ans += dfs(pos - 1, low, 0, nx, ny);
    }
    if(not leadx and not leady){
        D[pos][high][low] = ans;
    }    
    return ans;
}

llt digitDP(llt n){
    G.clear();
    while(n){
        G.emplace_back(n % 10);
        n /= 10;
    }
    auto t = dfs(G.size()-1, 0, 0, true, true);
    auto t2 = dfs(G.size()-1, 0, 1, true, true);
    return t + t2;
}


class Solution {
public:
    long long countNoZeroPairs(long long n) {
        memset(D, -1, sizeof(D));
        auto t = digitDP(n);
        return t;
    }
};

